#include "../../BSTree/BsharpTree.h"

BsharpTree::BsharpTree(string nombreArchivo, unsigned short tamanioNodo) {

	this->tamanioNodo = tamanioNodo;
	this->nombreArchivo = nombreArchivo;
	this->archivoBinario = new ArchivoBinario(nombreArchivo, tamanioNodo);
	this->getRaiz();
	this->nodoActual = NULL;
}

BsharpTree::~BsharpTree() {
	if (this->nodoRaiz)
		delete nodoRaiz;
	if (this->nodoActual)
		delete nodoActual;
	delete this->archivoBinario;
}

Node* BsharpTree::getRaiz() {
	//Lee el primer nodo del archivo -> la raiz
	if (!this->nodoRaiz) {
		this->nodoRaiz = new Node(0, 0, this->tamanioNodo);
		escribirNodo(this->nodoRaiz);
	}

	return this->nodoRaiz;

}

void BsharpTree::copiarClaveHoja(Clave* clave, string& puntero) {
	//Copio el valor de la clave

	const char separador1 = '/';
	const char separador2 = '%';

	puntero = puntero + clave->getClave();
	puntero.push_back(separador2);

	//Copio la referencia a registro
	std::string auxiliar;
	std::stringstream out;

	out << clave->getReferencia();
	auxiliar = out.str();
	puntero = puntero + auxiliar;
	auxiliar.clear();
	puntero.push_back(separador1);


}

void BsharpTree::copiarClaveNoHoja(Clave* clave, string& puntero) {

	//Copio el valor de la clave

	const char separador1 = '/';
	const char separador2 = '%';

	puntero = puntero + clave->getClave();
	puntero.push_back(separador2);

	//Copio la referencia a registro
	std::string auxiliar;
	std::stringstream out;

	out << clave->getHijoDer();
	auxiliar = out.str();
	puntero = puntero + auxiliar;
	auxiliar.clear();
	puntero.push_back(separador1);
}

int BsharpTree::leerNodo(unsigned int numNodo, Node* nodoLeido) {
	string data;
	string dataAux;
	char resultado = 0;

	Clave* claveNueva = NULL;
	KeyNode* keyNode = new KeyNode();
	HeaderNodo headerNodo;
	Utilitaria* utilitaria = new Utilitaria();

	data = archivoBinario->Read(numNodo);
	unsigned int posicion = 0;
	unsigned int size = data.find_first_of('/');

	headerNodo.nivel = utilitaria->StringToInt(data.substr(posicion, size));

	posicion = size;
	size = data.find_first_of('/', posicion + 1);

	headerNodo.espacioLibre = utilitaria->StringToInt(data.substr(posicion + 1, (size - (posicion + 1))));

	posicion = size;
	size = data.find_first_of('/', size + 1);

	headerNodo.refNodo = utilitaria->StringToInt(data.substr(posicion + 1, (size - (posicion + 1))));

	//Seteo el espacio libre, el nivel y la referencia del nodo
	nodoLeido->setNivel(headerNodo.nivel);
	nodoLeido->setEspacioLibre(headerNodo.espacioLibre);
	nodoLeido->setRefNodo(headerNodo.refNodo);

	//Recorrer el buffer desde donde quedo hasta que supere
	//el espacio libre, interpretando clave por clave.

	posicion = size;
	size = data.find_first_of('/', size + 1);

	if (nodoLeido->getNivel() == 0) {
		while (size <= (data.length() - 1)) {


			dataAux = data.substr(posicion + 1, (size - (posicion + 1)));

			claveNueva = this->leerClaveHoja(dataAux);
			keyNode->insert(claveNueva);

			posicion = size;
			size = data.find_first_of('/', size + 1);
		}
	} else {
		while (size <= (data.length() - 1)) {


			dataAux = data.substr(posicion + 1, (size - (posicion + 1)));

			claveNueva = this->leerClaveNoHoja(dataAux);
			keyNode->insert(claveNueva);

			posicion = size;
			size = data.find_first_of('/', size + 1);
		}
	}

	//Agregar el la lista de claves (keynode) al nodo
	nodoLeido->setKeyNode(keyNode);

	//Seteo la posicion del nodo en el archivo
	nodoLeido->setPosicionEnArchivo(numNodo);

	data.clear();
	dataAux.clear();

	return resultado;
}

int BsharpTree::escribirNodo(Node* nodoNuevo) {
	int resultado  = 0;
	int numNodo = 0;
	const char separador1 = '/';

	// SE COPIA NIVEL
	string nodoSerializado;
	std::string auxiliar;

	std::stringstream out;

	out << nodoNuevo->getNivel();
	auxiliar = out.str();
	nodoSerializado = auxiliar;
	auxiliar.clear();
	nodoSerializado.push_back(separador1);

	// SE COPIA ESPACIO LIBRE

	std::stringstream out2;

	out2 << nodoNuevo->getEspacioLibre();
	auxiliar = out2.str();
	nodoSerializado = nodoSerializado + auxiliar;
	auxiliar.clear();
	nodoSerializado.push_back(separador1);

	// SE COPIA REFERENCIA

	std::stringstream out3;

	out3 << nodoNuevo->getRefNodo();
	auxiliar = out3.str();
	nodoSerializado = nodoSerializado + auxiliar;
	auxiliar.clear();
	nodoSerializado.push_back(separador1);

	//Creo Buffer

	KeyNode *set;

	//Obtener la lista de claves
	set = nodoNuevo->getKeyNode();

	//Recorrer la lista de claves copiando cada clave al buffer
	if (nodoNuevo->getNivel() == 0) {

		for (KeyNode::iterator iterClaves = set->begin(); iterClaves
				!= set->end(); ++iterClaves){

			this->copiarClaveHoja((Clave*) (*iterClaves), nodoSerializado);
		}
	} else {

		for (KeyNode::iterator iterClaves = set->begin(); iterClaves
				!= set->end(); ++iterClaves)
			this->copiarClaveNoHoja((Clave*) (*iterClaves), nodoSerializado);
	}

	cout<<"tamanioHeader: "<<this->getTamanioHeader()<<endl;
	//int tamHead= this->getTamanioHeader();

	int tnodoSerial = nodoSerializado.size();
	while (tnodoSerial<this->tamanioNodo) {
		nodoSerializado = nodoSerializado + "-";
		tnodoSerial = nodoSerializado.size();
	}


	numNodo = archivoBinario->posicion();
	nodoNuevo->setPosicionEnArchivo(numNodo);

	archivoBinario->Write(nodoSerializado);
	cout<<nodoSerializado<<endl;

	nodoSerializado.clear();

	return resultado;
}

int BsharpTree::escribirNodo(unsigned short numNodo, Node* nodoModif) {
	int resultado = 0;

	const char separador1 = '/';

	// SE COPIA NIVEL
	string nodoSerializado;
	std::string auxiliar;
	std::stringstream out1;
	out1 << nodoModif->getNivel();

	auxiliar = out1.str();
	nodoSerializado = auxiliar;
	auxiliar.clear();
	nodoSerializado.push_back(separador1);

	// SE COPIA ESPACIO LIBRE
	std::stringstream out2;
	out2 << nodoModif->getEspacioLibre();

	auxiliar = out2.str();
	nodoSerializado = nodoSerializado + auxiliar;
	auxiliar.clear();
	nodoSerializado.push_back(separador1);

	// SE COPIA CANTIDAD DE CLAVES
	std::stringstream out3;
	out3 << nodoModif->getRefNodo();

	auxiliar = out3.str();
	nodoSerializado = nodoSerializado + auxiliar;
	auxiliar.clear();
	nodoSerializado.push_back(separador1);

	//Creo Buffer
	KeyNode *set;
	//Obtener la lista de claves
	set = nodoModif->getKeyNode();

	//Recorrer la lista de claves copiando cada clave al buffer
	if (nodoModif->getNivel() == 0) {

		for (KeyNode::iterator iterClaves = set->begin(); iterClaves
				!= set->end(); ++iterClaves){

			this->copiarClaveHoja((Clave*) (*iterClaves), nodoSerializado);

			}
	} else {

		for (KeyNode::iterator iterClaves = set->begin(); iterClaves
				!= set->end(); ++iterClaves)
			this->copiarClaveNoHoja((Clave*) (*iterClaves), nodoSerializado);
	}

	nodoModif->setPosicionEnArchivo(numNodo);
	cout<<nodoSerializado<<endl;
	int tnodoSerial = nodoSerializado.size();
	while (tnodoSerial<this->tamanioNodo) {
		nodoSerializado = nodoSerializado + "-";
		tnodoSerial = nodoSerializado.size();
	}
	cout<<nodoSerializado<<endl;
	archivoBinario->SetPosicion(numNodo);
	archivoBinario->Write(nodoSerializado);
	nodoSerializado.clear();

	return resultado;
}

int BsharpTree::eliminarNodo(unsigned short posicion) {
	char resultado = 0;

	archivoBinario->deleteData(posicion);

	return resultado;
}

void BsharpTree::primero() {
	if (this->vacio())
		return;

	if ((this->nodoActual) && (this->nodoActual != this->nodoRaiz))
		delete this->nodoActual;

	//El nodo actual termina siendo el primer nodo hoja del arbol B#
	//(para recorridos)
	this->nodoActual = this->nodoRaiz;
	unsigned int refHijoIzq;
	//Busco hasta la hoja
	while (this->nodoActual->getNivel() != 0) {
		refHijoIzq = this->nodoActual->getHijoIzq();
		if (this->nodoActual != this->nodoRaiz)
			delete this->nodoActual;
		this->nodoActual = new Node(0, 0, this->tamanioNodo);
		this->leerNodo(refHijoIzq, this->nodoActual);
	}

	this->iterClavesActual = this->nodoActual->getKeyNode()->begin();
}

void BsharpTree::mayorOIgual(Clave* clave) {

	if ((!clave) || (this->vacio()))
		return;

	if ((this->nodoActual) && (this->nodoActual != this->nodoRaiz))
		delete this->nodoActual;

	this->nodoActual = this->buscarLugar(clave);
	this->iterClavesActual = this->nodoActual->getKeyNode()->find(clave);

	if (this->iterClavesActual == this->nodoActual->getKeyNode()->end()) {

		Clave* auxClave = this->nodoActual->getKeyNode()->findClaveSiguiente(
				clave);

		if (auxClave)
			this->iterClavesActual = this->nodoActual->getKeyNode()->find(
					auxClave);
		else {
			--this->iterClavesActual;
			auxClave = siguiente();
			if (auxClave)
				delete auxClave;
		}

	}
}

void BsharpTree::mayor(Clave* clave) {

	if ((!clave) || (this->vacio()))
		return;

	if ((this->nodoActual) && (this->nodoActual != this->nodoRaiz))
		delete this->nodoActual;

	this->nodoActual = this->buscarLugar(clave);
	this->iterClavesActual = this->nodoActual->getKeyNode()->find(clave);

	Clave* auxClave = NULL;

	if (this->iterClavesActual != this->nodoActual->getKeyNode()->end()) {
		auxClave = siguiente();
		if (auxClave)
			delete auxClave;
	} else {
		auxClave = this->nodoActual->getKeyNode()->findClaveSiguiente(clave);

		if (auxClave)
			this->iterClavesActual = this->nodoActual->getKeyNode()->find(
					auxClave);
		else {
			--this->iterClavesActual;
			auxClave = siguiente();
			if (auxClave)
				delete auxClave;
		}
	}
}

Clave* BsharpTree::siguiente() {

	if (!this->nodoActual)
		return NULL;

	unsigned int refHnoDer;

	//Se usa un while para evitar problemas al encontrar un nodo vacío.
	while (((refHnoDer = this->nodoActual->getHnoDer()) != 0)
			&& (this->iterClavesActual == this->nodoActual->getKeyNode()->end())) {
		delete this->nodoActual;
		this->nodoActual = new Node(0, 0, this->tamanioNodo);
		this->leerNodo(refHnoDer, this->nodoActual);
		this->iterClavesActual = this->nodoActual->getKeyNode()->begin();
	}

	if (this->iterClavesActual != this->nodoActual->getKeyNode()->end())
		return (*(this->iterClavesActual++))->copiar();

	return NULL;
}

bool BsharpTree::insertar(Clave* clave) {
	if (!clave)
		return false;

	if (this->vacio()) {

		this->nodoRaiz = new Node(0, 0, clave, this->tamanioNodo);

		this->escribirNodo(this->nodoRaiz);

	} else {
		//Se busca el nodo hoja donde se debe insertar la clave
		Node* nodoDestino = buscarLugar(clave);

		char codigo;
		nodoDestino->insertarClave(clave, &codigo);

		//Se verifica si la clave ya estaba insertada
		if (codigo == CodigoArbol::NO_MODIFICADO) {
			delete nodoDestino;
			return false;
		}

		//La clave queda insertada independientemente de si hay OVERFLOW o no.
		insertarInterno(nodoDestino, &codigo, clave);

		if (*nodoDestino == *(this->nodoRaiz))
			*(this->nodoRaiz) = *nodoDestino;

		delete nodoDestino; //No se libera la memoria de this->nodoRaiz ya que nodoDestino era una copia

	}

	return true;
}

void BsharpTree::insertarInterno(Node* &nodoDestino, char* codigo,
		Clave* claveInsertada) {

	if (*codigo == CodigoArbol::MODIFICADO) {
		//Se actualiza en disco el nodo modificado.

		this->escribirNodo(nodoDestino->getPosicionEnArchivo(), nodoDestino);
	} else if (*codigo == CodigoArbol::OVERFLOWARBOL) {
		cout<<"desborde"<<endl;

		Node* nodoPadre = this->buscarPadre(this->nodoRaiz, nodoDestino,
				claveInsertada);

		if (!nodoPadre) { //nodoDestino es la raiz.

			KeyNode* KeyNodeDerecho = nodoDestino->splitB(
					nodoDestino->getTamanioMinimo());
			Clave* clavePromocionada = NULL;
			Node *nuevoNodoDerecho = NULL, *nuevaRaiz = NULL;

			if (nodoDestino->getNivel() == 0) { //Si es hoja
				clavePromocionada = (*(KeyNodeDerecho->begin()))->copiar();
				nuevoNodoDerecho = new Node(clavePromocionada->getHijoDer(),
						nodoDestino->getNivel(), this->tamanioNodo);
				nuevoNodoDerecho->setKeyNode(KeyNodeDerecho);
				this->escribirNodo(nuevoNodoDerecho);
				nodoDestino->setHnoDer(nuevoNodoDerecho->getPosicionEnArchivo());
			} else {
				clavePromocionada = (*(KeyNodeDerecho->begin()));
				KeyNodeDerecho->erase(KeyNodeDerecho->begin());
				nuevoNodoDerecho = new Node(clavePromocionada->getHijoDer(),
						nodoDestino->getNivel(), this->tamanioNodo);
				nuevoNodoDerecho->setKeyNode(KeyNodeDerecho);
				this->escribirNodo(nuevoNodoDerecho);
			}

			//Se actualiza nodoDestino
			this->escribirNodo(nodoDestino);
			clavePromocionada->setHijoDer(
					nuevoNodoDerecho->getPosicionEnArchivo());

			nuevaRaiz = new Node(nodoDestino->getPosicionEnArchivo(),
					nodoDestino->getNivel() + 1, clavePromocionada,
					this->tamanioNodo);

			//Se escribe la nueva raíz
			this->escribirNodo(0, nuevaRaiz);
			nuevaRaiz->setPosicionEnArchivo(0);
			*(this->nodoRaiz) = *nuevaRaiz;
			delete nuevoNodoDerecho;
			delete nuevaRaiz;
			*codigo = CodigoArbol::MODIFICADO;

		} else {
			//Se realiza el split del nodo con overflow
			Clave* clavePromocionada = this->split(nodoDestino);
			cout<<"split"<<endl;
			nodoPadre->insertarClave(clavePromocionada, codigo);

			if (*nodoPadre == *(this->nodoRaiz))
				*(this->nodoRaiz) = *nodoPadre;

			//Llamada recursiva para chequear overflow en el padre
			insertarInterno(nodoPadre, codigo, claveInsertada);

			delete nodoPadre;
		}

	}

}

bool BsharpTree::eliminar(Clave* clave) {

	if ((!clave) || (this->vacio()))
		return false;

	Node* nodoTarget = buscarLugar(clave);

	Clave* claveBuscada = nodoTarget->buscar(clave);

	char codigo = 0;

	if ((claveBuscada) && (*claveBuscada == *clave)) {
		nodoTarget->eliminarClave(claveBuscada, &codigo);
		this->eliminarInterno(nodoTarget, &codigo, clave); //resuelve underflow y escribe en disco
	} else {
		delete nodoTarget;
		return false;
	}

	if ((this->nodoRaiz) && (nodoTarget) && (*nodoTarget == *(this->nodoRaiz)))
		*(this->nodoRaiz) = *nodoTarget;

	delete nodoTarget;

	return true;
}

void BsharpTree::eliminarInterno(Node* &nodoTarget, char* codigo,
		Clave* claveEliminada) {

	if (*codigo == CodigoArbol::MODIFICADO) {
		//Se actualiza en disco el nodo modificado.
		this->escribirNodo(nodoTarget->getPosicionEnArchivo(), nodoTarget);
	} else if (*codigo == CodigoArbol::UNDERFLOWARBOL) {
		//Puntero a la clave del nodo padre que se encuentra entre nodoTarget y su hermano izq
		Clave* clavePadreIzq = NULL;
		//Puntero a la clave del nodo padre que se encuentra entre nodoTarget y su hermano der
		Clave* clavePadreDer = NULL;
		Node *nodoPadre = this->buscarPadre(this->nodoRaiz, nodoTarget,
				claveEliminada);
		Node *nodoHnoDer = NULL, *nodoHnoIzq = NULL;

		if (!nodoPadre) {//nodoTarget es el nodo raíz, no se chequea underflow.
			*codigo = CodigoArbol::MODIFICADO;
			if (nodoTarget->getCantidadClaves() == 0) {
				this->eliminarNodo(nodoTarget->getPosicionEnArchivo());
				delete this->nodoRaiz;
				this->nodoRaiz = NULL;
			} else {
				this->escribirNodo(nodoTarget->getPosicionEnArchivo(),
						nodoTarget);
			}
		} else {

			//Se buscan los hermanos derecho e izquierdo de 'nodoTarget'

			//Se busca dentro del nodo padre la clave cuyo hijo derecho es nodoTarget
			KeyNode::iterator iterPadre;
			for (iterPadre = nodoPadre->getKeyNode()->begin(); (iterPadre
					!= nodoPadre->getKeyNode()->end())
					&& ((*iterPadre)->getHijoDer()
							!= nodoTarget->getPosicionEnArchivo()); ++iterPadre)
				;

			//Se verifica si nodoTarget tiene hermano derecho y hermano izquierdo
			if (iterPadre == nodoPadre->getKeyNode()->end()) {
				//nodoTarget es el hijo izquierdo de nodoPadre
				//nodoTarget no tiene hermano izquierdo;
				//Se tendrían que cargar el hno derecho
				iterPadre = nodoPadre->getKeyNode()->begin();
				nodoHnoDer = new Node(0, 0, this->tamanioNodo);
				this->leerNodo((*iterPadre)->getHijoDer(), nodoHnoDer);
				clavePadreDer = *iterPadre;
			} else if ((++iterPadre) == nodoPadre->getKeyNode()->end()) {
				//nodoTarget es el hijo derecho de la última clave del nodo
				//nodoTarget no tiene hermano derecho
				if ((--iterPadre) == nodoPadre->getKeyNode()->begin()) {
					nodoHnoIzq = new Node(0, 0, this->tamanioNodo);
					this->leerNodo(nodoPadre->getHijoIzq(), nodoHnoIzq);
					clavePadreIzq = *iterPadre;
				} else {
					nodoHnoIzq = new Node(0, 0, this->tamanioNodo);
					this->leerNodo((*(--iterPadre))->getHijoDer(), nodoHnoIzq);
					clavePadreIzq = *(++iterPadre);
				}
			} else {
				--iterPadre; //Lo decremento xq se incrementó en el 'else if' anterior
				if (iterPadre == nodoPadre->getKeyNode()->begin()) {
					nodoHnoIzq = new Node(0, 0, this->tamanioNodo);
					this->leerNodo(nodoPadre->getHijoIzq(), nodoHnoIzq);
					clavePadreIzq = *iterPadre;
				} else {
					nodoHnoIzq = new Node(0, 0, this->tamanioNodo);
					this->leerNodo((*(--iterPadre))->getHijoDer(), nodoHnoIzq);
					clavePadreIzq = *(++iterPadre);
				}
				nodoHnoDer = new Node(0, 0, this->tamanioNodo);
				this->leerNodo((*(++iterPadre))->getHijoDer(), nodoHnoDer);
				clavePadreDer = *iterPadre;
			}

			//Fin de la búsqueda de los nodos hermanos de 'nodoTarget'

			//Se intenta hacer una redistribución de claves con el hermano derecho de 'nodoTarget'.
			//Si esto no es posible, se intenta hacer una redistribución con el hermano izquierdo.
			bool pudoRedistribuir = false;

			if (nodoHnoDer) {
				if ((pudoRedistribuir = nodoHnoDer->puedePasarClaveHaciaIzq(
						nodoTarget, nodoPadre, clavePadreDer)))
					this->pasarClaveHaciaIzquierda(nodoTarget, nodoPadre,
							nodoHnoDer, clavePadreDer);
				else if (nodoHnoIzq) {
					if ((pudoRedistribuir
							= nodoHnoIzq->puedePasarClaveHaciaDer(nodoTarget,
									nodoPadre, clavePadreIzq)))
						this->pasarClaveHaciaDerecha(nodoTarget, nodoPadre,
								nodoHnoIzq, clavePadreIzq);
				}

				if (!pudoRedistribuir)
					this->pasarMaximoPosibleHaciaIzquierda(nodoTarget,
							nodoPadre, nodoHnoDer, clavePadreDer);

			} else { // tiene hermano izquierdo
				if ((pudoRedistribuir = nodoHnoIzq->puedePasarClaveHaciaDer(
						nodoTarget, nodoPadre, clavePadreIzq)))
					this->pasarClaveHaciaDerecha(nodoTarget, nodoPadre,
							nodoHnoIzq, clavePadreIzq);

				if (!pudoRedistribuir)
					this->pasarMaximoPosibleHaciaDerecha(nodoTarget, nodoPadre,
							nodoHnoIzq, clavePadreIzq);

			}

			if (!pudoRedistribuir) { //Se realiza la concatenación de 'nodoTarget' con un nodo hermano. Si es un nodo
				//interno, también se concatena con un separador del padre.

				bool pudoMerge = false;
				if ((*nodoPadre == *(this->nodoRaiz))
						&& (nodoPadre->getCantidadClaves() == 1)) {
					if (nodoHnoDer) {
						if ((pudoMerge = this->puedeMerge(nodoTarget,
								nodoHnoDer, nodoPadre->obtenerPrimeraClave()))) {
							this->merge(nodoTarget, nodoHnoDer,
									nodoPadre->obtenerPrimeraClave());
							*nodoPadre = *nodoTarget;
							nodoPadre->setPosicionEnArchivo(0);
							if (nodoTarget->getNivel() == 0)
								nodoPadre->setHijoIzq(0);
							//Se escribe la nueva raiz
							this->escribirNodo(
									nodoPadre->getPosicionEnArchivo(),
									nodoPadre);
							//Se elimina de disco el bloque que ocupaba nodoTarget
							this->eliminarNodo(
									nodoTarget->getPosicionEnArchivo());
						}

					} else {
						if ((pudoMerge = this->puedeMerge(nodoHnoIzq,
								nodoTarget, nodoPadre->obtenerPrimeraClave()))) {
							this->merge(nodoHnoIzq, nodoTarget,
									nodoPadre->obtenerPrimeraClave());
							*nodoPadre = *nodoHnoIzq;
							nodoPadre->setPosicionEnArchivo(0);
							if (nodoHnoIzq->getNivel() == 0)
								nodoPadre->setHijoIzq(0);
							//Se escribe la nueva raiz
							this->escribirNodo(
									nodoPadre->getPosicionEnArchivo(),
									nodoPadre);
							//Se elimina de disco el bloque que ocupaba nodoTarget
							this->eliminarNodo(
									nodoHnoIzq->getPosicionEnArchivo());
						}
					}

					if (!pudoMerge) {
						*codigo = CodigoArbol::MODIFICADO;
						this->eliminarInterno(nodoTarget, codigo,
								claveEliminada);
					}
				} else {

					if (nodoHnoDer) {
						if ((pudoMerge = this->puedeMerge(nodoTarget,
								nodoHnoDer, clavePadreDer))) {
							this->merge(nodoTarget, nodoHnoDer, clavePadreDer);
							nodoPadre->eliminarClave(clavePadreDer, codigo);
						}
					} else {
						if ((pudoMerge = this->puedeMerge(nodoHnoIzq,
								nodoTarget, clavePadreIzq))) {
							this->merge(nodoHnoIzq, nodoTarget, clavePadreIzq);
							nodoPadre->eliminarClave(clavePadreIzq, codigo);
						}
					}

					if (!pudoMerge) {
						*codigo = CodigoArbol::MODIFICADO;
						this->eliminarInterno(nodoTarget, codigo,
								claveEliminada);
					} else
						//Se resuelve posible underflow al eliminar la clave separadora. Si no hay underflow,
						//este método se encargará de escribir nodoPadre en disco.
						this->eliminarInterno(nodoPadre, codigo, claveEliminada);

				}
			}

			if (nodoHnoDer)
				delete nodoHnoDer;
			if (nodoHnoIzq)
				delete nodoHnoIzq;

			if (*nodoPadre == *(this->nodoRaiz))
				*(this->nodoRaiz) = *nodoPadre;

			delete nodoPadre;
			nodoPadre = NULL;
		}

	}

}

Clave* BsharpTree::buscar(Clave* clave) {

	if ((!clave) || (this->vacio()))
		return NULL;

	Node* nodo = this->buscarLugar(clave);

	KeyNode::iterator iter = nodo->getKeyNode()->find(clave);
	cout<<"iter; "<< (*iter)->getClave();

	Clave* claveBuscada = NULL;

	if (iter != nodo->getKeyNode()->end())
		claveBuscada = (*iter)->copiar();
	cout<<"clave buscada:" <<claveBuscada->getReferencia()<<endl;

	delete nodo;

	return claveBuscada;

}

int BsharpTree::modificar(Clave* claveVieja, Clave* claveNueva) {

	int resultado = CodigosResultadosIndices::CLAVE_NO_ENCONTRADA;

	Clave* claveBuscada = this->buscar(claveVieja);

	if (!claveBuscada)
		return resultado;

	if (*claveBuscada == *claveVieja) {

		claveNueva->setReferencia(claveBuscada->getReferencia());

		//Si no hubo cambios en la clave no hago nada!
		if (*claveVieja == *claveNueva)
			resultado = CodigosResultadosIndices::OK;
		else if (this->eliminar(claveVieja)) {
			if (this->insertar(claveNueva))
				resultado = CodigosResultadosIndices::OK;
			else
				resultado = CodigosResultadosIndices::CLAVE_DUPLICADA;
		}

	}

	delete claveBuscada;

	return resultado;

}

Node* BsharpTree::buscarPadre(Node* padre, Node* hijo, Clave* claveNodoHijo) {

	Node *auxNodo = NULL, *nuevoNodo = NULL;
	Clave* claveOrientadora = NULL;

	if ((!padre) || (!hijo) || (*hijo == *(this->nodoRaiz)))
		return NULL;

	if (padre->esPadre(hijo, claveOrientadora, claveNodoHijo)) {

		auxNodo = new Node(0, 0, this->tamanioNodo);
		//Devuelvo una copia del padre
		*auxNodo = *padre; //Operador =

	} else {

		if (claveOrientadora == NULL) {
			nuevoNodo = new Node(0, 0, this->tamanioNodo);
			this->leerNodo(padre->getHijoIzq(), nuevoNodo);
		} else {
			nuevoNodo = new Node(0, 0, this->tamanioNodo);
			this->leerNodo(claveOrientadora->getHijoDer(), nuevoNodo);
		}

		auxNodo = buscarPadre(nuevoNodo, hijo, claveNodoHijo);

		delete nuevoNodo;

	}

	return auxNodo;

}

Node* BsharpTree::buscarLugar(Clave* clave) {

	if (!clave)
		return NULL;

	//Se supone que el nodo raíz ya se encuentra cargado en memoria.
	return buscarLugarRecursivo(this->nodoRaiz, clave);
}

Node* BsharpTree::buscarLugarRecursivo(Node* nodo, Clave* clave) {

	Node *nuevoNodo = NULL, *auxNodo = NULL;

	Clave* claveResultante = nodo->buscar(clave);

	if (claveResultante == NULL) {

		if (nodo->getNivel() == 0) { //Nodo hoja
			auxNodo = new Node(0, 0, this->tamanioNodo);
			//Devuelvo una copia de 'nodo'
			*auxNodo = *nodo;
		} else {
			nuevoNodo = new Node(0, 0, this->tamanioNodo);
			this->leerNodo(nodo->getHijoIzq(), nuevoNodo);
			auxNodo = buscarLugarRecursivo(nuevoNodo, clave);
			delete nuevoNodo;
		}

	} else {

		if (claveResultante->getHijoDer() == 0) {//Nodo hoja
			auxNodo = new Node(0, 0, this->tamanioNodo);
			//Devuelvo una copia de 'nodo'
			*auxNodo = *nodo;

		} else {
			nuevoNodo = new Node(0, 0, this->tamanioNodo);
			this->leerNodo(claveResultante->getHijoDer(), nuevoNodo);
			auxNodo = buscarLugarRecursivo(nuevoNodo, clave);
			delete nuevoNodo;
		}

	}

	return auxNodo;

}

Clave* BsharpTree::split(Node* nodoTarget) {

	Clave* clavePromocionada;
	KeyNode* clavesMayores = nodoTarget->splitB(nodoTarget->getTamanioMinimo()); //En nodoTarget quedan las claves menores
	Node* nuevoNodo = NULL;

	if (nodoTarget->getNivel() == 0) { //Si es hoja
		nuevoNodo = new Node(nodoTarget->getHnoDer(), nodoTarget->getNivel(),
				nodoTarget->getTamanio());
		nuevoNodo->setKeyNode(clavesMayores);
		this->escribirNodo(nuevoNodo);
		nodoTarget->setHnoDer(nuevoNodo->getPosicionEnArchivo());
		clavePromocionada = (*(clavesMayores->begin()))->copiar();
	} else {
		clavePromocionada = (*(clavesMayores->begin()));
		clavesMayores->erase(clavesMayores->begin());
		nuevoNodo = new Node(clavePromocionada->getHijoDer(),
				nodoTarget->getNivel(), nodoTarget->getTamanio());
		nuevoNodo->setKeyNode(clavesMayores);
		this->escribirNodo(nuevoNodo);
	}

	clavePromocionada->setHijoDer(nuevoNodo->getPosicionEnArchivo());

	//Actualizo nodoTarget
	this->escribirNodo(nodoTarget->getPosicionEnArchivo(), nodoTarget);

	delete nuevoNodo;

	return clavePromocionada;
}

void BsharpTree::merge(Node* nodoIzquierdo, Node* &nodoDerecho,
		Clave* separador) {

	if (nodoIzquierdo->getNivel() == 0) { //nodoIzquierdo es un nodo hoja
		nodoIzquierdo->merge(nodoDerecho, NULL);
		nodoIzquierdo->setHnoDer(nodoDerecho->getHnoDer());
	} else {
		separador->setHijoDer(nodoDerecho->getHijoIzq());
		nodoIzquierdo->merge(nodoDerecho, separador->copiar());
	}

	nodoIzquierdo->actualizarEspacioLibre();

	this->eliminarNodo(nodoDerecho->getPosicionEnArchivo());
	this->escribirNodo(nodoIzquierdo->getPosicionEnArchivo(), nodoIzquierdo);

}

bool BsharpTree::puedeMerge(Node* nodoIzq, Node* nodoDer, Clave* separador) {

	KeyNode keyNode;
	KeyNode::iterator iter;

	for (iter = nodoIzq->getKeyNode()->begin(); iter
			!= nodoIzq->getKeyNode()->end(); ++iter)
		keyNode.insert(*iter);

	for (iter = nodoDer->getKeyNode()->begin(); iter
			!= nodoDer->getKeyNode()->end(); ++iter)
		keyNode.insert(*iter);

	if (nodoIzq->getNivel() != 0) {
		keyNode.insert(separador);
	}

	unsigned short i;
	iter = keyNode.begin();

	for (i = 0; iter != keyNode.end(); ++iter) {
		i += (*iter)->getTamanioEnDisco();
	}

	bool puede = (i <= nodoIzq->getTamanioEspacioClaves());

	keyNode.clear();
	return (puede);
}

void BsharpTree::pasarClaveHaciaIzquierda(Node* nodoDestino, Node* nodoPadre,
		Node* nodoHnoDer, Clave* clavePadre) {

	char codigo;
	unsigned short bytesRequeridos = nodoDestino->obtenerBytesRequeridos();
	unsigned short tamanioClavePadre = clavePadre->getTamanioEnDisco();
	KeyNode* setIntercambio = NULL;
	Clave* clavePromocionada = NULL;

	nodoPadre->extraerClave(clavePadre);

	if (nodoDestino->getNivel() == 0) {

		setIntercambio = nodoHnoDer->cederBytes(bytesRequeridos);

		clavePromocionada = nodoHnoDer->obtenerPrimeraClave()->copiar();

	} else {

		clavePadre->setHijoDer(nodoHnoDer->getHijoIzq());

		if (tamanioClavePadre < bytesRequeridos)
			setIntercambio = nodoHnoDer->cederBytes(bytesRequeridos
					- tamanioClavePadre);

		clavePromocionada = nodoHnoDer->extraerPrimeraClave();

		nodoHnoDer->setHijoIzq(clavePromocionada->getHijoDer());

		nodoDestino->insertarClave(clavePadre, &codigo);

	}

	clavePromocionada->setHijoDer(nodoHnoDer->getPosicionEnArchivo());

	nodoPadre->insertarClave(clavePromocionada, &codigo);

	if (setIntercambio) {
		nodoDestino->recibir(setIntercambio);
		delete setIntercambio;
	}

	//Se actualizan los nodos en disco
	this->escribirNodo(nodoDestino->getPosicionEnArchivo(), nodoDestino);
	this->escribirNodo(nodoPadre->getPosicionEnArchivo(), nodoPadre);
	this->escribirNodo(nodoHnoDer->getPosicionEnArchivo(), nodoHnoDer);

}

void BsharpTree::pasarMaximoPosibleHaciaIzquierda(Node* nodoDestino,
		Node* nodoPadre, Node* nodoHnoDer, Clave* &clavePadre) {

	char codigo;
	unsigned short bytesAEntregar;
	unsigned short tamanioClavePadre = clavePadre->getTamanioEnDisco();
	KeyNode* setIntercambio = NULL;
	Clave* clavePromocionada = NULL;

	bytesAEntregar = nodoHnoDer->obtenerBytesSobreMinimo();

	if (bytesAEntregar > 0) {

		nodoPadre->extraerClave(clavePadre);

		if (nodoDestino->getNivel() == 0) {

			setIntercambio = nodoHnoDer->cederBytes(bytesAEntregar);

			clavePromocionada = nodoHnoDer->obtenerPrimeraClave()->copiar();

		} else {

			clavePadre->setHijoDer(nodoHnoDer->getHijoIzq());

			if (tamanioClavePadre < bytesAEntregar)
				setIntercambio = nodoHnoDer->cederBytes(bytesAEntregar
						- tamanioClavePadre);

			clavePromocionada = nodoHnoDer->extraerPrimeraClave();

			nodoHnoDer->setHijoIzq(clavePromocionada->getHijoDer());

			nodoDestino->insertarClave(clavePadre, &codigo);
		}

		clavePromocionada->setHijoDer(nodoHnoDer->getPosicionEnArchivo());

		nodoPadre->insertarClave(clavePromocionada, &codigo);
		clavePadre = clavePromocionada;

		if (setIntercambio) {
			nodoDestino->recibir(setIntercambio);
			delete setIntercambio;
		}

		//Se actualizan los nodos en disco
		this->escribirNodo(nodoDestino->getPosicionEnArchivo(), nodoDestino);
		this->escribirNodo(nodoPadre->getPosicionEnArchivo(), nodoPadre);
		this->escribirNodo(nodoHnoDer->getPosicionEnArchivo(), nodoHnoDer);

	}

}

void BsharpTree::pasarClaveHaciaDerecha(Node* nodoDestino, Node* nodoPadre,
		Node* nodoHnoIzq, Clave* clavePadre) {

	char codigo;
	unsigned short bytesRequeridos = nodoDestino->obtenerBytesRequeridos();
	unsigned short tamanioClavePadre = clavePadre->getTamanioEnDisco();
	KeyNode* setIntercambio = NULL;
	Clave* clavePromocionada = NULL;

	nodoPadre->extraerClave(clavePadre);

	if (nodoDestino->getNivel() == 0) {

		setIntercambio = nodoHnoIzq->cederBytes(bytesRequeridos, false);

		clavePromocionada = (*(setIntercambio->begin()))->copiar();

	} else {

		clavePadre->setHijoDer(nodoDestino->getHijoIzq());

		if (tamanioClavePadre < bytesRequeridos) {
			setIntercambio = nodoHnoIzq->cederBytes(bytesRequeridos
					- tamanioClavePadre, false);
			clavePromocionada = *(setIntercambio->begin());
			setIntercambio->erase(setIntercambio->begin());
		} else
			clavePromocionada = nodoHnoIzq->extraerUltimaClave();

		nodoDestino->setHijoIzq(clavePromocionada->getHijoDer());
		nodoDestino->insertarClave(clavePadre, &codigo);
	}

	clavePromocionada->setHijoDer(nodoDestino->getPosicionEnArchivo());

	nodoPadre->insertarClave(clavePromocionada, &codigo);

	if (setIntercambio) {
		nodoDestino->recibir(setIntercambio);
		delete setIntercambio;
	}

	//Se actualizan los nodos en disco
	this->escribirNodo(nodoDestino->getPosicionEnArchivo(), nodoDestino);
	this->escribirNodo(nodoPadre->getPosicionEnArchivo(), nodoPadre);
	this->escribirNodo(nodoHnoIzq->getPosicionEnArchivo(), nodoHnoIzq);

}

void BsharpTree::pasarMaximoPosibleHaciaDerecha(Node* nodoDestino,
		Node* nodoPadre, Node* nodoHnoIzq, Clave* &clavePadre) {

	char codigo;
	unsigned short bytesAEntregar;
	unsigned short tamanioClavePadre = clavePadre->getTamanioEnDisco();
	KeyNode* setIntercambio = NULL;
	Clave* clavePromocionada = NULL;

	bytesAEntregar = nodoHnoIzq->obtenerBytesSobreMinimo(false);

	if (bytesAEntregar > 0) {

		nodoPadre->extraerClave(clavePadre);

		if (nodoDestino->getNivel() == 0) {

			setIntercambio = nodoHnoIzq->cederBytes(bytesAEntregar, false);

			clavePromocionada = (*(setIntercambio->begin()))->copiar();

		} else {

			clavePadre->setHijoDer(nodoDestino->getHijoIzq());

			if (tamanioClavePadre < bytesAEntregar) {
				setIntercambio = nodoHnoIzq->cederBytes(bytesAEntregar
						- tamanioClavePadre, false);
				clavePromocionada = *(setIntercambio->begin());
				setIntercambio->erase(setIntercambio->begin());
			} else
				clavePromocionada = nodoHnoIzq->extraerUltimaClave();

			nodoDestino->setHijoIzq(clavePromocionada->getHijoDer());
			nodoDestino->insertarClave(clavePadre, &codigo);

		}

		clavePromocionada->setHijoDer(nodoDestino->getPosicionEnArchivo());

		nodoPadre->insertarClave(clavePromocionada, &codigo);
		clavePadre = clavePromocionada;

		if (setIntercambio) {
			nodoDestino->recibir(setIntercambio);
			delete setIntercambio;
		}

		//Se actualizan los nodos en disco
		this->escribirNodo(nodoDestino->getPosicionEnArchivo(), nodoDestino);
		this->escribirNodo(nodoPadre->getPosicionEnArchivo(), nodoPadre);
		this->escribirNodo(nodoHnoIzq->getPosicionEnArchivo(), nodoHnoIzq);

	}

}
